import UIKit
/*
89-合并两个有序数组
 中文：https://leetcode-cn.com/problems/merge-sorted-array/
 英文：https://leetcode.com/problems/merge-sorted-array/
*/

class Solution {
    func merge(_ nums1: inout [Int], _ m: Int, _ nums2: [Int], _ n: Int) {
        var insertIndex = m + n - 1
        var m = m - 1, n = n - 1
        while m >= 0, n >= 0 {
            if nums1[m] < nums2[n] {
                nums1[insertIndex] = nums2[n]
                insertIndex -= 1
                n -= 1
            }else {
                nums1[insertIndex] = nums1[m]
                insertIndex -= 1
                m -= 1
            }
        }
        
        while m >= 0 {
            nums1[insertIndex] = nums1[m]
            insertIndex -= 1
            m -= 1
        }
        while n >= 0 {
            nums1[insertIndex] = nums2[n]
            insertIndex -= 1
            n -= 1
        }
    }
}
var nums1 = [1, 3, 5, 0, 0, 0]
var nums2 = [2, 5, 6]
let solution: Solution = Solution()
solution.merge(&nums1, 3, nums2, 3)
nums1
